package org.jspar.route;

import java.util.ArrayList;
import java.util.List;

import org.jspar.tile.Position;
import org.jspar.tile.Tile;
import org.jspar.util.Identity;
import org.jspar.util.ListUtil;

public class Trail implements Comparable<Trail> {

	private int cost;
	private Expansion expansion;
	private Object used;
	private List<Tile> tr = new ArrayList<Tile>();
	private int direction;
	private Expansion jEx;
	private int page;
	private GlobalRouting routing;

	public Trail(Tile ti, Expansion ex, int page, int dir, GlobalRouting globalRouting) {
		cost = 0;
		expansion = ex;
		used = null;
		direction = dir;
		if (ti != null) {
			tr.add(ti);
			ex.addSeen(ti);
		}
		this.page = page;
		this.routing = globalRouting;
	}

	public List<Tile> tiles() {
		return tr;
	}

	public Expansion expansion() {
		return expansion;
	}

	public int cost() {
		return cost;
	}
	
	public int page() {
		return page;
	}

	public void incCost(int amount) {
		cost += amount;
	}

	public Expansion jEx() {
		throw new RuntimeException("not completed");
	}
	
	@Override
	public int compareTo(Trail o) {
		return cost - o.cost;
	}

	public int computeCost() {
		cost = trail_cost_est(tr, expansion, page).result();
		return cost;
	}
	
	public Trail add_to_trail(Tile ti) {
		direction = GlobalRouting.toggleDirection(direction);
		jEx = null;
		if (ti != null) {
			tiles().add(ti);
			computeCost();
			for (Tile tl : tiles()) {
				Arc a = (Arc) tl.content();
				a.remove_trailA(this);
				a.insertTrailA(this);
			}
		}
		return this;
	}
	
	private TrailCost trail_cost_est(List<Tile> tiles, Expansion expansion,
			int page) {
		int length = 0;
		int cornerCount = 1;
		Position corn = new Position(-1, -1);

		Tile lasTile = tiles.size() > 0 ? tiles.get(0) : null;
		Tile curTile = tiles.size() > 1 ? tiles.get(1) : null;
		Tile nexTile = tiles.size() > 2 ? tiles.get(2) : null;

		if (lasTile == null) {
			throw new RuntimeException("trail_cost_est: passed a NULL tile");
		}

		Position[] pos = new Position[1];
		length_to_next_corner(lasTile, curTile, corn, false, pos);
		corn = pos[0];
		Expansion[] nearestExT = new Expansion[1];
		int lookaheadEstimate = expansion.distance_to_go(corn, nearestExT);
		Expansion nearestEx = nearestExT[0];

		if (nearestEx != null) {
			Tile termTile = nearestEx.initialMove(routing, page);
			if (termTile == lasTile) {
				length += corn.manhatanDistance(nearestEx.terminal().getGlobalPosition());
			} else
				length = lookaheadEstimate;
		}
		
		Arc a = (Arc) lasTile.content();
		int congestionCost = a.congestionCost();

		lasTile = curTile;
		curTile = nexTile;
		nexTile = ((nexTile != null) && (tiles.size() > 3)) ?
				tiles.get(3) : null;

		for (int it = 4; it < tiles.size(); ++it) {
			Tile tl = tiles.get(it);
			a = (Arc) lasTile.content();
			congestionCost += a.congestionCost();
			if (curTile != null) {
				length += length_to_next_corner(lasTile, curTile, corn, true, pos);
				corn = pos[0];
				cornerCount += 1;
			} else {
				length += corn.manhatanDistance(expansion.terminal().getGlobalPosition());
			}
			lasTile = curTile;
			curTile = nexTile;
			nexTile = tl;
			if (lasTile == null)
				break;
		}
		return new TrailCost(length, lookaheadEstimate, cornerCount,
				congestionCost);
	}

	private static int length_to_next_corner(Tile t1, Tile t2, Position org,
			boolean useOrg, Position[] pos) {
		if (t1 == null) {
			if (t2 == null)
				return 0;
			else {
				pos[0] = t2.getBounds().center();
				if (!useOrg)
					return t2.width() / 2;
				return Math.abs(org.x() - t2.right());
			}
		}

		Arc a1 = (Arc) t1.content();
		if (t2 == null) {
			pos[0] = t1.getBounds().center();
			if (!useOrg)
				return t1.width() / 2;
			return Math.abs(org.x() - t1.right());
		}
		
		Arc a2 = (Arc) t2.content();
		if (a1.page() == GlobalRouting.VERT && a2.page() == GlobalRouting.HORZ) {
			int[] q = LocalRoute.findIntersection(t1.x(), t1.right(), t2.y(), t2.bottom());
			int midpnt = (q[0] + q[1]) / 2;
			pos[0] = new Position(t1.y() + (t1.height() / 2), midpnt);
			return !useOrg ? t1.width() / 2 : Math.abs(org.y() - midpnt);
		}
		
		if (a1.page() == GlobalRouting.HORZ && a2.page() == GlobalRouting.VERT) {
			int[] q = LocalRoute.findIntersection(t2.y(), t2.bottom(), t1.x(), t1.right());
			int midpnt = (q[0] + q[1]) / 2;
			pos[0] = new Position(midpnt, t1.y() + (t1.height() / 2));
			return !useOrg ? t1.width() / 2 : Math.abs(org.x() - midpnt);
		}
		pos[0] = t2.getBounds().center();
		if (a2.page() == GlobalRouting.HORZ)
			return !useOrg ? (t2.height() + t1.height()) / 2 : Math.abs(org.y() - pos[0].y());
		return !useOrg ? (t2.width() + t1.width()) / 2 : Math.abs(org.x() - pos[0].x());
	}

	public boolean isValid() {
		for (int i = 0; i < tr.size(); ++i) {
			Tile tl = tr.get(i);
			if (i == 0 && jEx != null) {
				Tile termTile = jEx.initialMove(routing, GlobalRouting.HORZ);
				if (termTile != tl) {
					return false;
				}
			}

			if (i < tr.size() - 1) {
				if (tile_contacts_tile_p(tl, tr.get(i + 1)) == false) {
					return false;
				}
			} else {
				Tile termTile = expansion.initialMove(routing, GlobalRouting.HORZ);
				if (termTile != tl) {
					return false;
				}
			}
		}
		return true;
	}

	public static boolean tile_contacts_tile_p(Tile t1, Tile t2) {
		return definite_overlap_p(t1.x(), t1.right(), t2.y(), t2.bottom())
				&& definite_overlap_p(t2.x(), t2.right(), t1.y(), t1.bottom());
	}

	public static boolean definite_overlap_p(int a1, int a2, int b1, int b2) {
		return (a1 < b2) && (a2 > b1);
	}

	public int direction() {
		return direction;
	}

	public List<Expansion> check_for_termination() {
		if (tr == null || tr.isEmpty()) {
			throw new RuntimeException(
					"check_for_termination:  trail component tr is NULL");
		}

		Arc a = (Arc) tr.get(0).content();

		Expansion parent = expansion;
		List<Expansion> terminationCandidateList = new ArrayList<Expansion>();
		Trail besTrail = null;

		for (Trail temp : a.getTrails()) {
			if (temp != besTrail
					&& temp.meets_termination_conditions_p(parent,
							besTrail)) {
				besTrail = temp;
				if (!terminationCandidateList.contains(temp.expansion))
					terminationCandidateList.add(temp.expansion);
			}
		}
		return terminationCandidateList;
	}

	public boolean meets_termination_conditions_p(
			Expansion parentEx, Trail besTrail) {
		if (expansion.net() == parentEx.net()
				&& !ListUtil.isMember(expansion, parentEx.getSiblings(),
						new Identity<Expansion>())
				&& (besTrail == null || cost < besTrail.cost || (besTrail.jEx != null &&
						cost == besTrail.cost))) {
			return true;
		}
		return false;
	}

	public Trail copy() {
		Trail _new = new Trail(null, expansion, page, direction, routing);
	    _new.cost = cost;
	    _new.tr = new ArrayList<Tile>(tr);
	    _new.jEx = jEx;
	    _new.used = used;
	    return _new;
	}

	public boolean breakCostTie(Trail tr2) {
		if (!isValid())
			return (false);
		if (! tr2.isValid())
			return true;

		TrailCost totalCost1 = trail_cost_est(tr, expansion, page);

		TrailCost totalCost2 = trail_cost_est(tr2.tr, tr2.expansion, tr2.page);

		if (totalCost1.result() < totalCost2.result())
			return (true);
		if (totalCost1.result() > totalCost2.result())
			return (false);
		if (totalCost1.congestionCost < totalCost2.congestionCost)
			return (true);
		if (totalCost1.congestionCost > totalCost2.congestionCost)
			return (false);
		if (totalCost1.cornerCount < totalCost2.cornerCount)
			return (true);
		if (totalCost1.cornerCount > totalCost2.cornerCount)
			return (false);
		if (totalCost1.length > totalCost2.length)
			return (false);
		if (totalCost1.length < totalCost2.length)
			return true;
		if (totalCost1.lookaheadEstimate < totalCost2.lookaheadEstimate)
			return true;
		if (totalCost1.lookaheadEstimate > totalCost2.lookaheadEstimate)
			return false;
		if (jEx != null)
			return true;
		if (tr2.jEx != null)
			return false;
		return true;
	}

	public void setJoinExpansion(Expansion e) {
		jEx = e;
	}

	public Trail flip() { // trail_flip
		throw new RuntimeException();
	}

	public void delete_trail() {
		pull_trail_from_all_arcs();
		expansion.remove_trailE(this);
	}

	private void pull_trail_from_all_arcs() {
	    for (Tile t : tr) {
	    	((Arc)t.content()).remove_trailA(this);
	    }
	}

}
